
type graphe = (string * string list ref) list

class graph =
object (this)

val mutable g = Obj.magic None 

method reset_graph = g <- []

method print_graph = print_endline "\nPrint_Graph : ";
	List.iter (fun ( (ps:string), (pa:string list ref)) -> 
	print_string ps;  List.iter (fun x -> print_string (" -> "^x)) !pa; print_string "\n   |   \n") g; 
	print_endline "\n\nEnd Print_Graph";

method private isinListe l e= List.mem e l

method get_graph = g
method set_graph newG = g <- newG

method private isinGraphe s = 
    let rec parc s = function
        [] -> false
        |(ps,(pa:string list ref))::l when s = ps -> true
        |(ps,(pa:string list ref))::l -> parc s l
    in parc s g

method private deleteDoublon = function
	 [] -> []
       |e::l when (List.exists (fun x -> x=e) l) -> (this#deleteDoublon l)
       |e::l -> e::(this#deleteDoublon l)

method private add_succ (s:string) (sa:string list ref) = 
	let rec parc (s:string) (sa:string list ref) = function
	  [] -> ()
	| (ps,(pa:string list ref))::l when s = ps -> pa := this#deleteDoublon (!pa@(!sa))
	| (ps,(pa:string list ref))::l -> parc s sa l
	in parc s sa g

method add_arc (s:string) (sa:string list ref) = if (this#isinGraphe s) 
                                                          then this#add_succ s sa
                                                          else g <- g@[s,sa](*;
						 this#print_graph*)

method private getSucc s = 
    let rec parc (graphe:graphe) ps = match graphe with
  [] -> failwith "Accès à un sommet non existant"
 |(ps, pa)::reste -> if s = ps 
		       then pa
  		       else parc reste s
    in parc g s

method private parcours aetevisite avisiter fAjout f =
   match avisiter with 
     [] -> ()
     |s::reste ->  
            if (this#isinListe aetevisite s) then 
	         this#parcours aetevisite reste fAjout f                
            else begin
              f s;              
	      let pa = this#getSucc s in              
	      let resteavisiter = fAjout reste pa in	          
	      let cequiaetevisite = s::aetevisite in              
	      this#parcours cequiaetevisite resteavisiter fAjout f
            end


method private enfiler (file:string list) (listelement:string list ref) =
    file@(!listelement)

method private empiler (pile:string list) (listelement:string list ref) = !listelement@pile

method parcProf sommet (f:string->unit) = this#parcours [] [sommet] this#empiler f  

method parcLarg sommet (f:string->unit) = this#parcours [] [sommet] this#enfiler f

end
